An Lộc Sơn dân tộc Đột Quyết, người Liễu Thành, Doanh Châu (營州; nay là Triều Dương, Liêu Ninh). Ông vốn có tên là Loát Lạc Sơn (軋犖山), mang họ Khang (姓康). Sau vì cha ông mất, mẹ ông cải giá với An Diên Yển (安延偃) nên ông lấy họ An và thay tên là Lộc Sơn. Tên Lộc Sơn phiên âm từ chữ Lushan, theo tiếng bản tộc có nghĩa là "ánh sáng".

Năm 724, An Lộc Sơn phạm tội ăn trộm dê, bị Tiết độ sứ U châu[3] của nhà Đường là Trương Thủ Khuê bắt giam. Khi sắp bị hành hình, Lộc Sơn kêu to:"Đại nhân không đi giết giặc Phiên, lại ở đây đánh chết Lộc Sơn, chẳng có uy danh gì cả!"

Trương Thủ Khuê thấy Lộc Sơn cao to trắng trẻo, lời nói khác thường, bèn thu nhận làm tuỳ tùng. Thấy ông dũng cảm, khoẻ mạnh, Thủ Khuê phong ông làm Tróc sinh tướng và nhận làm con nuôi. Sau này Thủ Khuê có công lao ngoài biên ải, được Đường Huyền Tông gọi về triều cất nhắc làm Thừa tướng.

Tương truyền, có lần Lộc Sơn rửa chân cho Thủ Khuê, thấy có bảy cái nốt ruồi đen ở bàn chân. Thấy Lộc Sơn ngắm nhìn bảy cái nốt ruồi, Thủ Khuê nói:"Phú quý ta có được đều ở bảy cái nốt ruồi đó"

Lộc Sơn bèn đáp:"Tiểu nhân ở cả hai bàn chân đều có như vậy"

Trương Thủ Khuê kinh ngạc, sai Lộc Sơn ngửa bàn chân xem, quả nhiên như vậy. Thủ Khuê đoán sau này ít ra Lộc Sơn cũng làm đến ngôi vị Tiết độ sứ, từ đó càng yêu quý Lộc Sơn hơn.